package Year2021;

public class 发码称重 {
    static int[] stack = new int[1000000];
    static int[] check = new int[1000000];
    //static int[] a = {1,2,3,4,5,6,7,8,9,10};
    static int[] a = {1,2,3};
    static int[] res = new int[1000000000];
    static int len;
    static int top = 0;
    static int total = 0;
    static int N = 3;
    public static void main(String[] args) {
        fun2(0);
        System.out.println("解空间："+total);
        for (int i = len-1; i > 0; i--) {
            System.out.print(res[i]+"\t");
            if((i+1) % 10 == 0)
                System.out.println();
        }

        System.out.println();
        System.out.println();
        quickSortArray(res,0,len-1);
        for (int i = len-1; i > 0; i--) {
            System.out.print(res[i]+"\t");
            if((i+1) % 10 == 0)
                System.out.println();
        }
        int result = 0;
        for (int i = 0; i < len; i++) {
            if(res[i] > 0 && res[i] != res[i-1])
                result++;
        }
        System.out.println();
        System.out.println("结果为："+result);
    }
    public static void fun2(int n){
        if(n == N){
            int sum = 0;
            for (int i = 0; i < top; i++) {
                System.out.print(stack[i]+"\t");
                if(stack[i] == 0)
                    sum += a[i];
                else if(stack[i] == 1)
                    sum -= a[i];
                else
                    continue;
            }
            res[len++] = sum;
            System.out.println();
            total++;
            return;
        }
        for (int i = 0; i <= 2; i++) {  // C (n,r) n个里面取r个元素，进行组合
            stack[top++] = i;
            fun2(n+1);
            top--;
        }
    }
    public static int[] quickSortArray(int[] array,int start, int end){
        int pivot = array[start];
        int i = start;
        int j = end;
        while (i<j) {
            while ((i<j)&&(array[j]>pivot)) {
                j--;
            }
            while ((i<j)&&(array[i]<pivot)) {
                i++;
            }
            if ((array[i]==array[j])&&(i<j)) {
                i++;
            } else {
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        if (i-1>start)
            array=quickSortArray(array,start,i-1);
        if (j+1<end)
            array=quickSortArray(array,j+1,end);
        return array;
    }
}
